#include "myGraph.h"
#include <bits/stdc++.h>
using namespace std;

EdgeNode::EdgeNode()
{
    dest = -1;
    link = NULL;
}

EdgeNode::EdgeNode(int dest, EdgeNode *link)
{
    this->dest = dest;
    this->link = link;
}

EdgeNode::~EdgeNode()
{
}

int EdgeNode::getDest()
{
    return this->dest;
}

EdgeNode *EdgeNode::getNext()
{
    return this->link;
}

void EdgeNode::setDest(int dest)
{
    this->dest = dest;
}

void EdgeNode::setNext(EdgeNode *link)
{
    this->link = link;
}

VertexNode::VertexNode()
{
    data = 0;
    firstEdge = NULL;
}

VertexNode::VertexNode(char data, EdgeNode *firstEdge)
{
    this->data = data;
    this->firstEdge = firstEdge;
}

VertexNode::~VertexNode()
{
}

char VertexNode::getData()
{
    return this->data;
}

EdgeNode *VertexNode::getFirstEdge()
{
    return this->firstEdge;
}

void VertexNode::setData(char data)
{
    this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode *firstEdge)
{
    this->firstEdge = firstEdge;
}

MyGraph::MyGraph()
{
    nodeNum = 0;
    edgeNum = 0;
    VexList = NULL;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char *nodeList, int *edgeStartList, int *edgeEndList)
{
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    VexList = new VertexNode[nodeNum];
    for (int i = 0; i < nodeNum; i++)
    {
        VexList[i].setData(nodeList[i]);
    }
    for (int j = 0; j < edgeNum; j++)
    {
        VexList[edgeStartList[j]].firstEdge = new EdgeNode(edgeEndList[j], VexList[edgeStartList[j]].firstEdge);
        VexList[edgeEndList[j]].firstEdge = new EdgeNode(edgeStartList[j], VexList[edgeEndList[j]].firstEdge);
    }
}

MyGraph::~MyGraph()
{

}

int MyGraph::getNodeNum()
{
    return this->nodeNum;
}

int MyGraph::getEdgeNum()
{
    return this->edgeNum;
}

string MyGraph::printGraph()
{
    string ans;
    
    for (int i = 0; i < nodeNum; i++)
    {
        string p;
        p = p + VexList[i].data + ":";
        for (EdgeNode *ads = VexList[i].firstEdge; ads != NULL; ads = ads->link)
        {
            if(ads==NULL)break;
            p = p + " " ;
            p=p+VexList[ads->dest].data;
        }
        ans = ans + p ;
        if(i!=nodeNum-1)ans=ans+"\n";
    }
    return ans;
}

void MyGraph::DFS(int v, bool *visited, string &result)
{
    result += (VexList[v].data);
    result += ' ';
    for (EdgeNode *ads = VexList[v].firstEdge; ads != NULL; ads = ads->link)
    {
        if (!visited[ads->dest])
        {
            visited[ads->dest] = true;
            DFS(ads->dest, visited, result);
        }
    }
}

string MyGraph::graph_DFS_Traverse()
{
    string ans;
    bool *visit = new bool[nodeNum];
    memset(visit, 0, sizeof(visit));
    visit[0]=true;
    DFS(0, visit, ans);
    return ans;
}

void MyGraph::BFS(int v, bool *visited, string &result)
{
    queue<VertexNode> q;
    q.push(VexList[v]);
    while (!q.empty())
    {
        VertexNode su = q.front();
        result += q.front().data;
        result += " ";
        q.pop();
        for (EdgeNode *ads = su.firstEdge; ads != NULL; ads = ads->link)
        {
            if (!visited[ads->dest])
            {
                visited[ads->dest] = true;
                q.push(VexList[ads->dest]);
            }
        }
    }
}

string MyGraph::graph_BFS_Traverse()
{
    string ans;
    bool *visit = new bool[nodeNum];
    memset(visit, 0, sizeof(visit));
    visit[0]=true;
    BFS(0,visit,ans);
    return ans;
}

using namespace std;
int main()
{
int nodeNum = 9;
int edgeNum = 10;
char nodeList[9] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};
int edgeStartList[10] = {0, 0, 0, 1, 1, 4, 2, 3, 5, 7};
int edgeEndList[10] = {1, 2, 3, 2, 4, 6, 5, 5, 7, 8};
MyGraph g(nodeNum, edgeNum, nodeList, edgeStartList, edgeEndList);
cout << g.printGraph() << endl;
cout << g.graph_DFS_Traverse() << endl;
cout << g.graph_BFS_Traverse() << endl;
system("pause");
return 0;
}
